package 剑指offer;

public class _33二叉搜索树的后序遍历序列 {
    public static boolean verifyPostorder(int[] postorder) {
        // 二叉树的后序遍历： 左右根。
        // 数组最后一个数是根节点，左侧小于根的所有节点为左子树，右侧的为右子树
        // 根据上述规则递归
        int length = postorder.length;
        if(postorder == null) {
            return false;
        }
        if(length == 0) {
            return true;
        }
        return verifyPostorder(postorder, 0, length-1);
    }
    public static boolean verifyPostorder(int[] postorder, int start, int end) {
        if(start == end) {
            return true;
        }

        int root = postorder[end];

        // 在二叉搜索树中左子树结点的值小于根节点
        int i = start;
        for(; i < end; ++i) {
            if(postorder[i] > root) {
                break;
            }
        }
        int j = i;
        for(; j < end; ++j) {
            if(postorder[j] < root) {
                return false;
            }
        }
        // 判断左子树是不是二叉搜索树
        boolean left = true;
        if(i > start) {
            left = verifyPostorder(postorder, start, i-1);
        }
        boolean right = true;
        if(i <= end) {
            right = verifyPostorder(postorder,i, end-1);
        }
        return right && left;
    }

    public static void main(String[] args) {
        int[] p = {1,3,2,6,5};
        System.out.println(verifyPostorder(p));
    }
//    public boolean verifyPostorder(int[] postorder) {
//        if (postorder == null) {
//            return false;
//        }
//        return verifyPostorderOFBSTHelper(postorder, 0, postorder.length - 1);
//    }
//    public boolean verifyPostorderOFBSTHelper(int[] postorder, int start, int end){
//        //递归出口
//        if(start >= end){
//            return true;
//        }
//        //后序遍历根节点
//        int root = postorder[end];
//        int i = start;
//        //找出所有小于根的左树值,走到最后一个
//        while (i < end && postorder[i] < root) {
//            i++;
//        }
//        //判断后面的值是否都大于root，及右子树大于根
//        for (int j = i; j < end; j++) {
//            if(postorder[j] < root){
//                return false;
//            }
//        }
//        return verifyPostorderOFBSTHelper(postorder, start, i-1)
//                && verifyPostorderOFBSTHelper(postorder, i, end-1);
//    }
}
